home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 401-425 / disk_419 / yacc / src.lzh / Src / closure.c < prev    next >
C/C++ Source or Header  |  1990-07-14  |  4KB  |  266 lines
  1. #include "defs.h"
  2.  
  3. short *itemset;
  4. short *itemsetend;
  5. unsigned *ruleset;
  6.  
  7. static unsigned *first_derives;
  8. static unsigned *EFF;
  9.  
  10.  
  11. set_EFF()
  12. {
  13.     register unsigned *row;
  14.     register int symbol;
  15.     register short *sp;
  16.     register int rowsize;
  17.     register int i;
  18.     register int rule;
  19.  
  20.     rowsize = WORDSIZE(nvars);
  21.     EFF = NEW2(nvars * rowsize, unsigned);
  22.  
  23.     row = EFF;
  24.     for (i = start_symbol; i < nsyms; i++)
  25.     {
  26.     sp = derives[i];
  27.     for (rule = *sp; rule > 0; rule = *++sp)
  28.     {
  29.         symbol = ritem[rrhs[rule]];
  30.         if (ISVAR(symbol))
  31.         {
  32.         symbol -= start_symbol;
  33.         SETBIT(row, symbol);
  34.         }
  35.     }
  36.     row += rowsize;
  37.     }
  38.  
  39.     reflexive_transitive_closure(EFF, nvars);
  40.  
  41. #ifdef    DEBUG
  42.     print_EFF();
  43. #endif
  44. }
  45.  
  46.  
  47. set_first_derives()
  48. {
  49.   register unsigned *rrow;
  50.   register unsigned *vrow;
  51.   register int j;
  52.   register unsigned mask;
  53.   register unsigned cword;
  54.   register short *rp;
  55.  
  56.   int rule;
  57.   int i;
  58.   int rulesetsize;
  59.   int varsetsize;
  60.  
  61.   rulesetsize = WORDSIZE(nrules);
  62.   varsetsize = WORDSIZE(nvars);
  63.   first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
  64.  
  65.   set_EFF();
  66.  
  67.   rrow = first_derives + ntokens * rulesetsize;
  68.   for (i = start_symbol; i < nsyms; i++)
  69.     {
  70.       vrow = EFF + ((i - ntokens) * varsetsize);
  71.       cword = *vrow++;
  72.       mask = 1;
  73.       for (j = start_symbol; j < nsyms; j++)
  74.     {
  75.       if (cword & mask)
  76.         {
  77.           rp = derives[j];
  78.           while ((rule = *rp++) >= 0)
  79.         {
  80.           SETBIT(rrow, rule);
  81.         }
  82.         }
  83.  
  84.       mask <<= 1;
  85.       if (mask == 0)
  86.         {
  87.           cword = *vrow++;
  88.           mask = 1;
  89.         }
  90.     }
  91.  
  92.       vrow += varsetsize;
  93.       rrow += rulesetsize;
  94.     }
  95.  
  96. #ifdef    DEBUG
  97.   print_first_derives();
  98. #endif
  99.  
  100.   FREE(EFF);
  101. }
  102.  
  103.  
  104. closure(nucleus, n)
  105. short *nucleus;
  106. int n;
  107. {
  108.     register int ruleno;
  109.     register unsigned word;
  110.     register unsigned mask;
  111.     register short *csp;
  112.     register unsigned *dsp;
  113.     register unsigned *rsp;
  114.     register int rulesetsize;
  115.  
  116.     short *csend;
  117.     unsigned *rsend;
  118.     int symbol;
  119.     int itemno;
  120.  
  121.     rulesetsize = WORDSIZE(nrules);
  122.     rsp = ruleset;
  123.     rsend = ruleset + rulesetsize;
  124.     for (rsp = ruleset; rsp < rsend; rsp++)
  125.     *rsp = 0;
  126.  
  127.     csend = nucleus + n;
  128.     for (csp = nucleus; csp < csend; ++csp)
  129.     {
  130.     symbol = ritem[*csp];
  131.     if (ISVAR(symbol))
  132.     {
  133.         dsp = first_derives + symbol * rulesetsize;
  134.         rsp = ruleset;
  135.         while (rsp < rsend)
  136.         *rsp++ |= *dsp++;
  137.     }
  138.     }
  139.  
  140.     ruleno = 0;
  141.     itemsetend = itemset;
  142.     csp = nucleus;
  143.     for (rsp = ruleset; rsp < rsend; ++rsp)
  144.     {
  145.     word = *rsp;
  146.     if (word == 0)
  147.         ruleno += BITS_PER_WORD;
  148.     else
  149.     {
  150.         mask = 1;
  151.         while (mask)
  152.         {
  153.         if (word & mask)
  154.         {
  155.             itemno = rrhs[ruleno];
  156.             while (csp < csend && *csp < itemno)
  157.             *itemsetend++ = *csp++;
  158.             *itemsetend++ = itemno;
  159.             while (csp < csend && *csp == itemno)
  160.             ++csp;
  161.         }
  162.  
  163.             mask <<= 1;
  164.             ++ruleno;
  165.         }
  166.     }
  167.     }
  168.  
  169.     while (csp < csend)
  170.     *itemsetend++ = *csp++;
  171.  
  172. #ifdef    DEBUG
  173.   print_closure(n);
  174. #endif
  175. }
  176.  
  177.  
  178.  
  179. finalize_closure()
  180. {
  181.   FREE(itemset);
  182.   FREE(ruleset);
  183.   FREE(first_derives + ntokens * WORDSIZE(nrules));
  184. }
  185.  
  186.  
  187. #ifdef    DEBUG
  188.  
  189. print_closure(n)
  190. int n;
  191. {
  192.   register short *isp;
  193.  
  194.   printf("\n\nn = %d\n\n", n);
  195.   for (isp = itemset; isp < itemsetend; isp++)
  196.     printf("   %d\n", *isp);
  197. }
  198.  
  199.  
  200. print_EFF()
  201. {
  202.     register int i, j, k;
  203.     register unsigned *rowp;
  204.     register unsigned word;
  205.     register unsigned mask;
  206.  
  207.     printf("\n\nEpsilon Free Firsts\n");
  208.  
  209.     for (i = start_symbol; i < nsyms; i++)
  210.     {
  211.     printf("\n%s", symbol_name[i]);
  212.     rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
  213.     word = *rowp++;
  214.  
  215.     mask = 1;
  216.     for (j = 0; j < nvars; j++)
  217.     {
  218.         if (word & mask)
  219.         printf("  %s", symbol_name[start_symbol + j]);
  220.  
  221.         mask <<= 1;
  222.         if (mask == 0)
  223.         {
  224.         word = *rowp++;
  225.         mask = 1;
  226.         }
  227.     }
  228.     }
  229. }
  230.  
  231.  
  232. print_first_derives()
  233. {
  234.   register int i;
  235.   register int j;
  236.   register unsigned *rp;
  237.   register unsigned cword;
  238.   register unsigned mask;
  239.  
  240.   printf("\n\n\nFirst Derives\n");
  241.  
  242.   for (i = start_symbol; i < nsyms; i++)
  243.     {
  244.       printf("\n%s derives\n", symbol_name[i]);
  245.       rp = first_derives + i * WORDSIZE(nrules);
  246.       cword = *rp++;
  247.       mask = 1;
  248.       for (j = 0; j <= nrules; j++)
  249.         {
  250.       if (cword & mask)
  251.         printf("   %d\n", j);
  252.  
  253.       mask <<= 1;
  254.       if (mask == 0)
  255.         {
  256.           cword = *rp++;
  257.           mask = 1;
  258.         }
  259.     }
  260.     }
  261.  
  262.   fflush(stdout);
  263. }
  264.  
  265. #endif
  266.